package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月22日
*时间：下午5:58:42
*/
public class Q41 {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        int length = nums.length;
        int rs = Integer.MIN_VALUE;
        int max[] = new int[length];
        max[0] = nums[0];
        if (rs < max[0]) {
            rs = max[0];
        }
        for (int i = 1; i < length; i++) {
            max[i] = (max[i - 1] < 0 ? 0 : max[i - 1]) + nums[i];
            if (rs < max[i]) {
                rs = max[i];
            }
        }
        return rs;
    }

    @Test
    public void testA() {
        int[] nums = { -2, 2, -3, 4, -1, 2, 1, -5, 3 };
        System.out.println(maxSubArray(nums));
    }
}
